Search for: All records

In the Zero-Knowledge Proof (ZKP) of a disjunctive statement, P and V agree on B fan-in 2 circuits C0, . . . , CB−1 over a field F; each circuit has n_in inputs, n_× multiplications, and one output. P’s goal is to demonstrate the knowledge of a witness (id ∈ [B], w ∈ F^n_in ), s.t. Cid (w) = 0 where neither w nor id is revealed. Disjunctive statements are effective, for example, in implementing ZKP based on sequential execution of CPU steps. This paper studies ZKP (of knowledge) protocols over disjunctive statements based on Vector OLE. Denoting by λ the statistical security parameter and let ρ \in^\Delta max{log |F|, λ}, the previous state-of-the-art protocol Robin (Yang et al. CCS’23) required (n_in +3n_×) log |F|+O(ρB) bits of communication with O(1) rounds, and Mac'n'Cheese (Baum et al. CRYPTO’21) required (n_in +n_×) log |F|+2n×ρ+O(ρ logB) bits of communication with O(logB) rounds, both in the VOLE-hybrid model. Our novel protocol LogRobin++ achieves the same functionality at the cost of (n_in+n_×) log |F|+O(ρ logB) bits of communication with O(1) rounds in the VOLE-hybrid model. Crucially, LogRobin++ takes advantage of two new techniques – (1) an O(logB)-overhead approach to prove in ZK that an IT-MAC commitment vector contains a zero; and (2) the realization of VOLE-based ZK over a disjunctive statement, where P commits only to w and multiplication outputs of Cid (w) (as opposed to prior work where P commits to w and all three wires that are associated with each multiplication gate). We implemented LogRobin++ over Boolean (i.e., F2) and arithmetic (i.e., F_2^61−1) fields. In our experiments, including the cost of generating VOLE correlations, LogRobin++ achieved up to 170× optimization over Robin in communication, resulting in up to 7× (resp. 3×) wall-clock time improvements in a WAN-like (resp. LAN-like) setting. 

We explore Zero-Knowledge Proofs (ZKPs) of statements expressed as programs written in high-level languages, e.g., C or assembly. At the core of executing such programs in ZK is the repeated evaluation of a CPU step, achieved by branching over the CPU’s instruction set. This approach is general and covers traversal-execution of a program’s control flow graph (CFG): here CPU instructions are straight-line program fragments (of various sizes) associated with the CFG nodes. This highlights the usefulness of ZK CPUs with a large number of instructions of varying sizes. We formalize and design an efficient tight ZK CPU, where the cost (both computation and communication, for each party) of each step depends only on the instruction taken. This qualitatively improves over state of the art, where cost scales with the size of the largest CPU instruction (largest CFG node). Our technique is formalized in the standard commit-and-prove paradigm, so our results are compatible with a variety of (interactive and non-interactive) general-purpose ZK. We implemented an interactive tight arithmetic (over F261−1) ZK CPU based on Vector Oblivious Linear Evaluation (VOLE) and compared it to the state-of-the-art non-tight VOLE-based ZK CPU Batchman (Yang et al. CCS’23). In our experiments, under the same hardware configuration, we achieve comparable performance when instructions are of the same size and a 5-18× improvement when instructions are of varied size. Our VOLE-based tight ZK CPU (over F261−1) can execute 100K (resp. 450K) multiplication gates per second in a WAN-like (resp. LAN-like) setting. It requires ≤ 102 Bytes per multiplication gate. Our basic building block, ZK Unbalanced Read-Only Memory, may be of independent interest. 

Consider the following two fundamental open problems in complexity theory: • Does a hard-on-average language in NP imply the existence of one-way functions? • Does a hard-on-average language in NP imply a hard-on-average problem in TFNP (i.e., the class of total NP search problem)? Our main result is that the answer to (at least) one of these questions is yes. Both one-way functions and problems in TFNP can be interpreted as promise-true distributional NP search problems—namely, distributional search problems where the sampler only samples true statements. As a direct corollary of the above result, we thus get that the existence of a hard-on-average distributional NP search problem implies a hard-on-average promise-true distributional NP search problem. In other words, It is no easier to find witnesses (a.k.a. proofs) for efficiently-sampled statements (theorems) that are guaranteed to be true. This result follows from a more general study of interactive puzzles—a generalization of average-case hardness in NP—and in particular, a novel round-collapse theorem for computationallysound protocols, analogous to Babai-Moran’s celebrated round-collapse theorem for informationtheoretically sound protocols. As another consequence of this treatment, we show that the existence of O(1)-round public-coin non-trivial arguments (i.e., argument systems that are not proofs) imply the existence of a hard-on-average problem in NP/poly.